/**
 * Brute Force - Multiply
 * Time O(N) | Space O(1)
 * https://leetcode.com/problems/powx-n/
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
 var myPow = (x, n) => {
    if (n < 0) {
        x = (1 / x);
        n = (-n);
    }

    return getPow(x, n);/* Time O(N) */
}

var getPow = (x, n, pow = 1) => {
    for (let i = 0; i < n; i++) {/* Time O(N) */
        pow = pow * x;
    }

    return pow;
}

/**
 * DFS 
 * Time (log(N)) | Space O(log(N))
 * https://leetcode.com/problems/powx-n/
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = (x, n) => {
    const isBaseCase1 = ((x === 1.0) || (n === 0));
    if (isBaseCase1) return 1;

    const isBaseCase2 = (n === 1);
    if (isBaseCase2) return x;

    const isEven = ((n % 2) === 0);
    if (isEven) return myPow((x * x), (n / 2));/* Time O(log(N)) | Space O(log(N)) */

    const isOdd = ((n % 2) === 1);
    if (isOdd) return (x * myPow(x, (n - 1)));/* Time O(log(N)) | Space O(log(N)) */

    return (1 / myPow(x, -n));
};

/**
 * DFS
 * Time (log(N)) | Space O(log(N))
 * https://leetcode.com/problems/powx-n/
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = (x, n) => {
    const isBaseCase = (n === 0);
    if (isBaseCase) return 1;

    const abs = Math.abs(n);
    const isEven = ((abs % 2) === 0);

    const power = isEven
        ? myPow((x * x), (abs / 2))             /* Time O(log(N)) | Space O(log(N)) */
        : (myPow((x * x), ((abs - 1) / 2)) * x);/* Time O(log(N)) | Space O(log(N)) */

    const isNegative = (n < 0);

    return isNegative
        ? (1 / power)
        : power;
};

/**
 * Fast Power - Recursive 
 * Time O(log(N)) | Space O(log(N))
 * https://leetcode.com/problems/powx-n/
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
 var myPow = (x, n) => {
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }

    return fastPow(x, n);/* Time O(log(N)) | Space O(log(N)) */
}

var fastPow = (x, n) => {
    const isBaseCase = n === 0;
    if (isBaseCase) return 1.0;

    const half = fastPow(x, n / 2);/* Time O(log(N)) | Space O(log(N)) */

    const isEven = ((n % 2) === 0);
    if (isEven) return (half * half);

    const isOdd = ((n % 2) === 1);
    if (isOdd) return ((half * half) * x);
}

/**
 * Fast Power - Iterative
 * Time O(log(N)) | Space O(1)
 * https://leetcode.com/problems/powx-n/
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
 var myPow = (x, n) => {
    if (n < 0) {
        x = (1 / x);
        n = (-n);
    }

    let [ pow, product ] = [ 1, x ];

    for (let i = n; (0 < i); i = (i >> 1)) {/* Time O(log(N)) */
        const isOdd = ((i % 2) === 1);
        if (isOdd) pow = (pow * product);

        product = (product * product);
    }

    return pow;
}
 
 /**
 * Number - Math
 * Time O(1) | Space O(1)
 * https://leetcode.com/problems/powx-n/
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
 var myPow = (x, n) => {
    return Math.pow(x,n).toFixed(5);
}
